"""The optimal algorithms 最优算法
The optimal algorithm for finding point cut sets based on depth traversing trees
利用深度遍历树找割点集的最优算法
割点指的是在原图中删除某一个节点就可以使图的连通度增加的节点
本算法使用 tarjan算法 (https://www.bilibili.com/video/BV19J411J7AZ)
用数组disc[u]存储DFS遍历到点u的时间,数组low[u]存储点u能追溯到最早的祖先节点。

对于点u来说有如下结论：
1.如果点u是DFS序列的根节点，则如果u有一个以上的孩子，则u是一个割点。
2.如果u不是DFS序列根节点，并且点u的任意后继v能追溯到最早的祖先节点low[v]>=用数组disc[u]，则u是一个割点。
"""
from collections import defaultdict
import igraph as ig
import matplotlib.pyplot as plt


class UndirectedGraph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.time = 0

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def _tarjan_ap_bridge(self, u, visited, parent, disc, low, cn, bridges):
        """
        使用深度优先遍历寻找割点
        :param u: 当前遍历的节点
        :param visited: 记录是否已经遍历
        :param parent: 在深度遍历树中当前节点u的父节点
        :param low: 当前节点u能追溯到最早的祖先节点, 也就是TNA(topmost neighboring ancestor)
        :param disc: dfs遍历到当前节点u的时间, 即遍历的第几个节点
        :param cn: 用于标记该节点是否是一个割点(cut node)
        :param bridges: 用于记录桥
        """
        children = 0
        visited[u] = True
        disc[u] = low[u] = self.time
        self.time += 1

        for v in self.graph[u]:
            if not visited[v]:
                parent[v] = u
                children += 1
                self._tarjan_ap_bridge(v, visited, parent, disc, low, cn, bridges)

                low[u] = min(low[u], low[v])

                # 割点条件1：u是根节点，且有两个或以上的子节点
                if parent[u] is None and children > 1:
                    cn[u] = True

                # 割点条件2：u不是根节点，且满足 low[v] >= disc[u]
                if parent[u] is not None and low[v] >= disc[u]:
                    cn[u] = True

                # 如果 u 到 v 的边是桥
                if low[v] > disc[u]:
                    bridges.append((u, v))

            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    def find_cn_and_bridges(self):
        visited = [False] * self.V  # 初始化节点的属性 [False, False, False, False, False]
        disc = [-1] * self.V
        low = [-1] * self.V
        parent = [None] * self.V
        cn = [False] * self.V  # 存储割点
        bridges = []

        for i in range(self.V):
            if not visited[i]:
                self._tarjan_ap_bridge(i, visited, parent, disc, low, cn, bridges)

        return [i for i, is_cn in enumerate(cn) if is_cn], bridges


# 示例使用
g = UndirectedGraph(7)
edges = [(0, 1), (0, 5), (0, 6), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (5, 6)]
for i, j in edges:
    g.add_edge(i, j)

cns, bridges = g.find_cn_and_bridges()
print("割点:", cns)
print("桥:", bridges)

# 绘图
n_vertices = 7
g = ig.Graph(n_vertices, edges)
id_list = list(range(0, 7))
g.vs["id"] = id_list
fig, ax = plt.subplots(figsize=(5, 5))
ig.plot(
    g,
    target=ax,
    # layout="circle",  # print nodes in a circular layout
    vertex_size=0.3,
    # vertex_frame_width=4.0,
    vertex_color="lightblue",
    vertex_frame_color="white",
    vertex_label=g.vs["id"],
    vertex_label_size=9.0,
    edge_color="gray",
    edge_arrow_size=0.01,
    margin=40
)
plt.show()
